#include "Sort.h"
#include "Stack.h"

// 打印函数
void PrintArray(int *a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 插入排序 0 ~ n-2   O(num) ~ O(num^2)
// 数据越接近有序 插入排序效率越高
void InsertSort(int *a, int n)
{
	int i, j, t;
	for (i = 0; i < n - 1; i++)
	{
		t = a[i + 1];
		for (j = i; j >= 0 && t < a[j]; j--)
			a[j + 1] = a[j];
		if (j != i)
			a[j + 1] = t;
	}
}

// 希尔排序
void ShellSort(int *a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int i, j, t;
		for (i = 0; i < n - gap; ++i)
		{
			t = a[i + gap];
			for (j = i; j >= 0 && t < a[j]; j -= gap)
			{
				a[j + gap] = a[j];
			}
			if (j != i)
				a[j + gap] = t;
		}
	}
}

void Swap(int *a, int *b)
{
	if (*a == *b)
		return;
	else
	{
		int t = *a;
		*a = *b;
		*b = t;
	}
}

// 选择排序：O(num^2) ~ O(num^2)
void SelectSort(int *a, int n)
{
	assert(a);
	// i：数据头 j：数据尾
	for (int i = 0, j = n - 1; i < j; ++i, --j)
	{
		// 假设最大值/最小值下标为i
		int m = i, M = i;
		// 遍历i后到j的所有数据 确定real_m/M
		for (int k = i + 1; k <= j; ++k)
		{
			if (a[k] < a[m])
				m = k;

			if (a[k] > a[M])
				M = k;
		}
		// 小值换到数据头
		Swap(&a[i], &a[m]);

		// 特殊情况: 原M即数据头即为max 经过第一次Swap后max和min换位
		// 此时要把M重定位
		if (i == M)
		{
			M = m;
		}
		// 大值换到数据尾
		Swap(&a[j], &a[M]);
	}
}

// 下调/筛选法建堆 O(N)  上调建堆O(NlogN)
// 升序建大堆--循环把大堆头放到尾部
void AdjustDwon(int *a, int size, int parent)
{
	// 设左孩子较小
	int child = parent * 2 + 1;
	// 当未达到堆末 进入循环
	while (child < size)
	{
		// 确定real小孩子
		// if (child + 1 < size && a[child + 1] < a[child])  //小堆

		// 确定real大孩子
		if (child + 1 < size && a[child + 1] > a[child]) // 大堆
		{
			++child;
		}

		// if (a[parent] > a[child])    //小堆
		if (a[parent] < a[child]) // 大堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int *a, int n)
{
	// 下调建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}
	// 排序
	int end = n - 1; // 此时end表示堆尾数据的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0); // 此时end表示传过去数据个数(n-1)
		--end;
	}
}

// 插入排序  O(num)~O(num^2)
// 冒泡排序  O(num)~O(num^2)
// 当数据有序 二者均为O(num) 当数据接近有序或局部有序 插排更优
void BubbleSort(int *a, int n)
{
	assert(a);
	int flag = 1;
	// n-1轮
	for (int i = 0; flag && i < n - 1; ++i)
	{
		flag = 0;
		// 首轮n-1次 依次递减
		for (int j = 0; j < n - 1 - i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j + 1], &a[j]);
				flag = 1;
			}
		}
	}
}

// 快速排序   O(num * logN)
int count = 0; // 测试递归次数
// 对任意区间抽三值取中位数
int GetMid_X(int *a, int begin, int end)
{
	int mid = (begin + end) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[end] < a[begin])
			return begin;
		else
			return end;
	}
	else // a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[end] > a[begin])
			return begin;
		else
			return end;
	}
}

// 霍尔版本 右找小 左找打 大小交换 依次递归
int PartQuickSort1(int *a, int begin, int end)
{
	int x = begin;
	int left = begin, right = end;

	// 确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);

	while (left < right)
	{
		// 右找小
		while (left < right && a[right] >= a[x])
			--right;

		// 左找大
		while (left < right && a[left] <= a[x])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[x], &a[left]);
	x = left;

	return x;
}

// 挖坑版本/教学版本 记录a[x]=key x位假想无效/置空
// 右找小入坑 坑位更新 左找大入坑 坑位更新 依次递归
int PartQuickSort2(int *a, int begin, int end)
{
	int x = begin;

	// 确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);
	int key = a[x];

	while (begin < end)
	{
		while (begin < end && a[end] >= key)
			--end;
		a[x] = a[end];
		x = end;

		while (begin < end && a[begin] <= key)
			++begin;
		a[x] = a[begin];
		x = begin;
	}

	a[x] = key;
	return x;
}

// 指针版本
int PartQuickSort3(int *a, int begin, int end)
{
	int x = begin;
	int prv = begin, cur = begin + 1;

	// 确定更合适的key
	int mid_x = GetMid_X(a, begin, end);
	Swap(&a[x], &a[mid_x]);

	while (cur <= end)
	{
		if (a[cur] < a[x] && ++prv != cur)
			Swap(&a[prv], &a[cur]);
		++cur;
	}
	Swap(&a[prv], &a[x]);
	x = prv;
	return x;
}

void QuickSort(int *a, int begin, int end)
{
	count++;
	if (begin >= end)
		return;

	if (end - begin > 10)
	{
		int x = PartQuickSort3(a, begin, end);

		QuickSort(a, begin, x - 1);
		QuickSort(a, x + 1, end);
	}
	else
		InsertSort(a + begin, end - begin + 1);
}

// 非递归版本
void QuickSort_NonRecursion(int *a, int begin, int end)
{
	ST st;
	StackInit(&st);

	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);

		int x = PartQuickSort3(a, begin, end);

		if (x + 1 < end)
		{
			StackPush(&st, x + 1);
			StackPush(&st, end);
		}
		// [begin, x-1] x [x+1, end]
		if (begin < x - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, x - 1);
		}
	}
	StackDestroy(&st);
}

//归并排序 时间复杂度：O(N*logN)   空间复杂度：O(N)
void PartMergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;

	//[begin, mid] [mid+1, end] 
	PartMergeSort(a, begin, mid, tmp);
	PartMergeSort(a, mid + 1, end, tmp);

	// [begin, mid] [mid+1, end]
	//   [i, mid]    [j, end]
	int i = begin, j = mid + 1, k = i;
	while (i <= mid && j <= end)
	{
		if (a[i] < a[j])
			tmp[k++] = a[i++];
		else
			tmp[k++] = a[j++];
	}

	while (i <= mid)
		tmp[k++] = a[i++];
	while (j <= end)
		tmp[k++] = a[j++]; 
	
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	//void PartMergeSort(int* a, int begin, int end, int* tmp);
	PartMergeSort(a, 0, n - 1, tmp);

	free(tmp);
}


void MergeSort_NonRecursion1(int *a, int n)
{
	int *tmp = (int *)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	int range = 1;
	while (range < n)
	{
		//printf("num = %d ->", range);
		for (int index = 0; index < n; index += 2 * range)
		{
			int i = index, k = i, end = index + range - 1;
			int j = index + range, End = index + 2 * range - 1;

			// 修正边界
			if (end >= n)
			{
				end = n - 1;
				j = n;
				End = n - 1;
			}
			else if (j >= n)
			{
				j = n;
				End = n - 1;
			}
			else if (End >= n)
				End = n - 1;
			//printf("[%d,%d]--[%d, %d]  ", i, end, j, End);
			
			// 数据排序
			while (i <= end && j <= End)
			{
				if (a[i] <= a[j])
					tmp[k++] = a[i++];
				else
					tmp[k++] = a[j++];
			}
			while (i <= end)
				tmp[k++] = a[i++];
			while (j <= End)
				tmp[k++] = a[j++];
		}
		//printf("\n");
		memcpy(a, tmp, sizeof(int) * n);
		range *= 2;
	}

	free(tmp);
}
void MergeSort_NonRecursion2(int *a, int n)
{
	int *tmp = (int *)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	int range = 1;
	while (range < n)
	{
		//printf("num=%d->", range);
		for (int index = 0; index < n; index += 2 * range)
		{
			int i = index, k = i, end = index + range - 1;
			int j = index + range, End = index + 2 * range - 1;

			if (end >= n || j >= n)
				break;
			else if (End >= n)
				End = n - 1;
			//printf("[%d,%d]--[%d,%d]  ", i, end, j, End);

			int m = End - i + 1;
			while (i <= end && j <= End)
			{
				if (a[i] <= a[j])
					tmp[k++] = a[i++];
				else
					tmp[k++] = a[j++];
			}
			while (i <= end)
				tmp[k++] = a[i++];
			while (j <= End)
				tmp[k++] = a[j++];
			memcpy(a + index, tmp + index, sizeof(int) * m);
		}
		//printf("\n");
		range *= 2;
	}
	free(tmp);
}

// 计数排序  时间复杂度：O(max(num, N)) 空间复杂度：O(num）
void CountSort(int *a, int n)
{
	// 确定最值
	int min = a[0], max = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int num = max - min + 1; // 最多有N个"连续"的数据
	// 开空间
	int *arr = (int *)malloc(sizeof(int) * num);
	if (arr == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memset(arr, 0, sizeof(int) * num);

	// a的数据映射到arr的下标 arr的值存储对应数据出现次数
	for (int i = 0; i < n; ++i)
		arr[a[i] - min]++;
	for (int i = 0, j = 0; i < num; ++i)
	{
		while (arr[i]--)
			a[j++] = i + min;
	}
}